using System;

namespace Algorithms
{
	public class SortingAlgorithms
	{
		// Insertion sort - Сортирвка вставками
		// Наихудший случай - n^2 (если массив отсортирован в обратном порядке) 
		// Наилучший случай - n (если массив уже отсортирован)
		// - используется много перестановок
		// + чем более отсортирован массив изначально, тем ближе время работы к n
		// Начиная со второго элемента массива ищем ему место в передней 
		// уже отсортированой части. Попутно сдвигаем все элементы на 1
		// освобождая место для сравниваемого элемента.
		public static void InsertionSort (int[] arr)
		{
			for (int i=1; i<arr.Length; i++) 
			{
				int key = arr [i];
				int j = i - 1;
				while (j>=0 && arr[j]>key) 
				{
					arr [j + 1] = arr [j];
					j--;
				} 
				arr [j+1] = key;
			}
		}

		//Selection sort - Сортировка выбором
		// Наихудший случай - n^2
		// Наилучший случай - n^2
		// - даже если массив уже отсортирован, алгоритм всеравно будет производить 
		//   сравнение каждого элемента с каждым
		// + в наихудшем случае требует n перестановок
		// Находим минимальный элемент массива и меняем его с первым
		// Повторяем процедуру для следующих, пока не дойдем до конца массива
		public static void SelectionSort(int[] arr){
			for (int currentIndex=0; currentIndex<arr.Length-1; ++currentIndex) {
				int minIndex = currentIndex;
				for (int i=currentIndex; i<arr.Length; ++i) {
					if (arr [i] < arr [minIndex])
						minIndex = i;
				}
				if (minIndex!=currentIndex)
				    AdditionalFunctions.Swap(ref arr[currentIndex], ref arr[minIndex]);
			}
		}

        // Merge sort - сортировка слиянием
        // Наихудший случай n*log(n)
        // Наилучший случай n*log(n)
        // - большой постоянный множитель (алгоритм плох для массивов небольшой длины)
        // - требуется большой обьем дополнительной паияти ( равен или больше самого массива)
        //   (не подходит, если есть ограничения по памяти)
        // - много копирований и перемещений (важно, если сортируются данные, а не указатели на них)
        // + Асимптотический рост времени работы алгоритма минимальный из возможных
        //   (доказано, что, если нет данных о взаимозависимости элементов - О(n*log(n)) - наилучший вариант
        // Разделяем массив на 2 подмассива. Пока левый и правый массив не будут отсортированы 
        // (отсортирован тот массив, в котором меньше 2-х элементов), рекурсивно их сортируем и
        // соединяем в один. Принцип соединения: пока не закончатся элементы, берем наименьший из двух верхних
        // и кладем в конец.
		public static void MergeSort(int[] arr){
            if (arr.Length < 2)
                return;
            int startIndex = 0;
            int endIndex = arr.Length - 1;
            int middleIndex = (startIndex + endIndex) / 2;
            int[] leftArray = new int[middleIndex - startIndex+1];
            SearchingAlgorithms.MyConstrainedCopy(arr, startIndex, leftArray, 0);
            int[] rightArray = new int[endIndex - middleIndex];
            SearchingAlgorithms.MyConstrainedCopy(arr, middleIndex+1, rightArray, 0);
            MergeSort(leftArray);
            MergeSort(rightArray);
            Merge(leftArray, rightArray, arr);
		}

	    public static void Merge(int[] left, int[] right, int[] res)
		{
			int ir = 0;
			int il = 0;
			int ires = 0;
			while (ir<right.Length && il<left.Length) 
			{
				if (left [il] < right [ir]) 
				{
					res [ires] = left [il];
					il++;
				} 
				else 
				{
					res [ires] = right [ir];
					ir++;
				}
				++ires;
			}
			for (int i=ir; i<right.Length; ++i, ++ires) {
				res [ires] = right [i];
			}
			
			for (int i=il; i<left.Length; ++i, ++ires) {
				res [ires] = left [i];
			}
		}
	}
}

